package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;

/**
 * 合并 K 个升序链表
 * 基于合并两个有序链表
 * 第一种方法是建一个空链表，然后遍历这k个链表集合，然后类似+=合并
 * 第二种方法分治法，比如链表[l1，l2，l3，l4，l5，l6]
 * 递归遍历到l1，l2后，将l1，l2合并,然后返回
 * 2025-02-26 16:02:54
 */
class MergeKSortedLists {

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 方法一：初始一个空链表ans，遍历list，将里面的每个链表跟ans合并
    // 时间复杂度：O(N*k^2)，空间复杂度：O(1),N链表的最大长度
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; i++) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
    // 合并两个有序链表：时间复杂度：O(N)，空间复杂度：O(1)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode pre = dummy;
        while (l1!=null&&l2!=null){
            if(l1.val<l2.val){
                pre.next = l1;
                l1=l1.next;
            }else{
                pre.next = l2;
                l2=l2.next;
            }
            pre=pre.next;
        }
        pre.next = l1==null?l2:l1;
        return dummy.next;
    }

    // 方法二：分治法
    // 时间复杂度：O(Nk*logK)，空间复杂度：O(logK)
//    public ListNode mergeKLists2(ListNode[] lists) {
//        ListNode merge = merge(lists, 0, lists.length-1);
//        return merge;
//    }
//    public ListNode merge(ListNode[] list , int l,int r){
//        if(l==r){
//            return list[l];
//        }
//        if(l>r){
//            return null;
//        }
//        int mid = (l+r)>>1;
//        return mergeTwoLists(merge(list,l,mid),merge(list,mid+1,r));
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new MergeKSortedLists().new Solution();
        
    }
}